Divide-and-Conquer Checkpointing for Arbitrary Programs with No User Annotation

摘要

Classical reverse-mode automatic differentiation (AD) imposes only a smallconstant-factor overhead in operation count over the original computation, buthas storage requirements that grow, in the worst case, in proportion to thetime consumed by the original computation. This storage blowup can beameliorated by checkpointing, a process that reorders application of classicalreverse-mode AD over an execution interval to tradeoff space \vs\ time.Application of checkpointing in a divide-and-conquer fashion to strategicallychosen nested execution intervals can break classical reverse-mode AD intostages which can reduce the worst-case growth in storage from linear tosublinear. Doing this has been fully automated only for computations ofparticularly simple form, with checkpoints spanning execution intervalsresulting from a limited set of program constructs. Here we show how thetechnique can be automated for arbitrary computations. The essential innovationis to apply the technique at the level of the language implementation itself,thus allowing checkpoints to span any execution interval.